// 实现 int sqrt(int x) 函数。
// 计算并返回 x 的平方根，其中 x 是非负整数。
// 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

// 示例 1:
// 输入: 4
// 输出: 2

// 示例 2:
// 输入: 8
// 输出: 2
// 说明: 8 的平方根是 2.82842..., 
//      由于返回类型是整数，小数部分将被舍去。

//这样查找耗时太长
// var mySqrt = function(x) {
//     for(let i = 0; i <= x; i++){
//     	if(i * i === x){
//     		return i;
//     	} else if(i * i > x){
//     		return i - 1;
//     	}
//     }
// };
//二分查找
var mySqrt2 = function(x) {
	if(x === 0){
		return 0;
	}
	let left = 0;
	let rigth = x;
	while(true){
		let mid = left + (right - left) / 2;
		if(mid * mid > x){
			rigth = mid - 1;
		} else {
			if((mid + 1) * (mid + 1) > x){
				return mid;
			}
			left = mid + 1;
		}
	}
};
console.log(mySqrt(8));